package com.ds.sort.impl;

import com.ds.sort.MySort;
import com.ds.util.ArrayUtil;

public class QuickSort implements MySort {
	
	@Override
	public <T extends Comparable<? super T>>  void sort(T[] array) {
		
		sort(array,0,array.length - 1);
		
		
	}
	
	private <T extends Comparable<? super T>>  void sort(T[] array,int left,int right) {
		
		if(left >= right) {
			return;
		}
		
		T flag = array[right]; 
		
		int i = left,j = right;
		
		while(i < j) {
			
			while(i < j && array[i].compareTo(flag) < 0) {
				i++;
			}
			while(j > i && array[j].compareTo(flag) >= 0) {
				j--;
			}
			if(i != j) {
				ArrayUtil.swap(array, i, j);
			}
		}
		ArrayUtil.swap(array, i, right);
		sort(array,left,i-1);
		sort(array,i+1,right);
		
	}
}
